package pers.tz.题目.leetcode.数组;

import pers.tz.common.ArrayUtils;

/**
 * 看到O(log n) 想到二分查找
 * 看到有序数组 想到二分查找
 *
 * @author irony
 * @date 2024-03-11
 */
public class leetcode_0034_在排序数组中查找元素的第一个和最后一个位置 {
//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//
// 示例 1：
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
//
// 示例 2：
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1]
//
// 示例 3：
//输入：nums = [], target = 0
//输出：[-1,-1]
//
// 提示：
// 0 <= nums.length <= 10⁵
// -10⁹ <= nums[i] <= 10⁹
// nums 是一个非递减数组
// -10⁹ <= target <= 10⁹

    public static void main(String[] args) {
        int[] ints = ArrayUtils.generateRandomArray(true, 5, 15);

        ints = new int[] {1, 3};
        ArrayUtils.printArray(ints);
        ArrayUtils.printArray(searchRange2(ints, 1));
    }

    // 最优解 O(log n)
    // 找到小于target的最右位置、小于target+1的最右位置
    public static int[] searchRange2(int[] nums, int target) {
        if (nums.length < 2) {
            return nums.length == 1 ? nums[0] == target ? new int[] {0, 0} : new int[] {-1, -1} : new int[] {-1, -1};
        }

        // 小于target的最右位置
        int L = binarySearch(nums, target) + 1;
        // 找到的值右边不一定是target
        if (L < 0 || L == nums.length || nums[L] != target) {
            return new int[] {-1, -1};
        }

        // 小于target + 1的最右位置
        return new int[] {L, binarySearch(nums, target + 1)};
    }

    private static int binarySearch(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        int ans = -1;

        while (L <= R) {
            int M = (L + R) / 2;

            // 小于target的最右位置
            if (nums[M] < target) {
                ans = M;
                L = M + 1;
            } else {
                R = M - 1;
            }
        }

        return ans;
    }

    // 可行解 O(N)
    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        if (nums.length == 0) {
            return res;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (res[0] == -1) {
                    res[0] = i;
                } else {
                    res[1] = i;
                    return res;
                }
            }
        }

        if (res[0] != -1) {
            return new int[] {-1, -1};
        }

        return res;
    }
}
